class Solution {
    /*
        思路1：使用标记数组的dfs回溯
        （ 使用标记数组获得的序列是符合字典序的）
        坑点：java拷贝问题
    */
    List<Integer> tmp = new ArrayList<>();
    List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        dfs(nums,1);
        return ans;
    }
    public void dfs(int[] nums,int cnt){
        if( cnt>nums.length ){
            ans.add(new ArrayList(tmp));
            return;
        }
        for(int i=0; i<nums.length; i++){
            if( tmp.indexOf(nums[i])>-1 )
                continue;
            tmp.add(nums[i]);
            dfs(nums,cnt+1);
            tmp.remove(tmp.size()-1);
        }
    }
}
class Solution {
    /*
        思路2：数组nums 划分成左右两个部分，左边的表示已经填过的数，右边表示待填的数，
              我们在回溯的时候只要动态维护这个数组即可。
        （这样生成的全排列并不是按字典序存储在答案数组）
        这个算法的时间复杂更优一点的原因？
        比如全排列1,2,3,4：我们已经排列好了（1，2）然后进入下次个递归，第一种思路依然是从1到4遍历，
        而第二种方法则是3，到4遍历即可。
        时间复杂度：O(n*n！)
    */
    List<Integer> list = new ArrayList<>();     // nums转化
    List<List<Integer>> ans = new ArrayList<>();// ans数组
    public List<List<Integer>> permute(int[] nums) {
        for (int num : nums) {
            list.add(num);
        }
        dfs(nums,0);
        return ans;
    }
    public void dfs(int[] nums, int cur) {
        if( cur==nums.length ){
            ans.add(new ArrayList<>(list));
            return;
        }
        /*  
            [0,cur-1]表示已经装填的数，[cur,len]表示为装填的数，
            每次我们把[cur,len]这些数移动到cur这个位置，这样已经装填的就是[0,cur+1]了
        */
        for(int i=cur; i<nums.length; i++){
            Collections.swap(list,i,cur);
            dfs(nums,cur+1);
            Collections.swap(list,i,cur);
        }
    }
}